class Solution931 {
    public static void main(String[] args) {
        int[][] arr = {{2,1,3},{6,5,4},{7,8,9}} ;
        minFallingPathSum(arr) ;
    }
    public static int minFallingPathSum(int[][] matrix) {
        int m = matrix.length ;
        int n = matrix[0].length ;
        int[][] dp = new int[m][n+2] ;

        for(int i = 0 ; i < m ; i ++){
            dp[i][0] = Integer.MAX_VALUE ;
            dp[i][n+1] = Integer.MAX_VALUE ;
        }

        for(int j=1 ; j <= n ; j ++){
            dp[0][j] = matrix[0][j-1] ;
        }

        for(int i=1 ; i < m ; i ++){
            for(int j=1 ; j <= n ; j ++){
                int min = Math.min(dp[i-1][j-1] ,Math.min(dp[i-1][j] , dp[i-1][j+1])) ;
                dp[i][j] = matrix[i][j-1] + min ;
            }
        }

        int min = Integer.MAX_VALUE ;
        for(int j=1 ; j <= n ; j ++){
            min =  Math.min(min , dp[m-1][j]) ;
        }
        return min ;

    }
}